package com.lun.swordtowardoffer2.c13;

import java.util.ArrayList;
import java.util.List;

public class Partition4Palindrome {

	public List<List<String>> partition(String str){
		List<List<String>> result = new ArrayList<>();
		List<String> path = new ArrayList<>();
		backtracking(str, 0, path, result);
		return result;
	}
	
	private void backtracking(String str, int startIndex, //
			List<String> path, List<List<String>> result) {
		
		if(startIndex == str.length()) {
			result.add(new ArrayList<>(path));
			return;
		}
		
		for(int i = startIndex; i < str.length(); i++) {
			
			if(isPalindrome(str, startIndex, i)) {
				path.add(str.substring(startIndex, i + 1));
				backtracking(str, i + 1, path, result);
				path.remove(path.size() - 1);
			}
		}
	}
	
	private boolean isPalindrome(String str, int start, int end) {
		while(start < end) {
			if(str.charAt(start++) != str.charAt(end--)) {
				return false;
			}
		}
		return true;
	}
}
